Năm 861 các thầy tu dòng Biển Đức đã dừng chân trên đỉnh ngọn đồi ở Vézelay, nhà thờ đầu tiên được xây dựng tại đây là vào năm 878 để lưu giữ những thánh tích của Maria Madalena do một tu sĩ mang về từ Saint-Maximin-la-Sainte-Baume ở vùng Provence. Với những thánh tích lưu giữ được, tu viện Vézelay trở thành một điểm dừng chân quan trọng của các con chiên trên Con đường hành hương Saint-Jacques-de-Compostelle. Năm 1096, một nhà thờ mới được xây dựng trên nền nhà thờ cũ, nhà thờ mới này được khánh thành ngày 21 tháng 4 năm 1104. Ngày 21 tháng 7 năm 1120, nhà thờ chịu một trận hỏa hoạn lớn (làm 1127 người chết), gian chính của nhà thờ được xây lại và hoàn thành năm 1138.

Tu viện Vézelay linh thiêng đã là nơi xuất phát của nhiều đoàn quân tham gia các cuộc Thập tự chinh, trong đó phải kể tới năm 1190 khi các đạo quân Anh do Richard Sư tử tâm và quân Pháp do Philippe-Auguste lãnh đạo xuất phát từ đây để tham gia cuộc Thập tự chinh thứ 3. Vị trí của tu viện giảm dần sau khi người ta phát hiện di hài của Maria Magdalena ở Saint-Maximin-la-Sainte-Baume và cho xây dựng một nhà thờ ở đây. Trong thời gian Cách mạng Pháp tu viện bị hủy hoại nghiêm trọng khi người ta khai thác đá từ đây để làm vật liệu, gần như chỉ còn phòng của hội đồng thầy tu là được giữ nguyên vẹn. Quá trình khôi phục tu viện bắt đầu diễn ra năm 1840 dưới sự chỉ đạo của kiến trúc sư Eugène Viollet-le-Duc và Prosper Mérimée. Từ năm 1920 Sainte Marie-Madeleine chính thức trở lại thành một nhà thờ và nơi dừng chân của các con chiên trên đường hành hương. Năm 1979 nhà thờ và khu đồi được UNESCO công nhận là Di sản thế giới.